package stu.day39_day.day42;

public class hw1 {

    public int findTargetSumWays(int[] nums, int target) {


        int sum = 0;
        int len = nums.length;
        for (int i=0;i<len;i++){
            sum += nums[i];
        }

        int a = (target+sum)/2;

        if(a<0){
            return 0;
        }
        if(((target+sum)%2)==1){
            return 0;
        }

        int[][] dp = new int[len+1][a+1];

        for (int i = 0; i < len+1; i++) {
            dp[i][0] = 1;
        }

        for (int i=1;i<len+1;i++){
            int num = nums[i-1];
            for (int j=0;j<a+1;j++){
                if(num<=j){
                    dp[i][j] = dp[i-1][j] + dp[i-1][j-num];
                }else {
                    dp[i][j] = dp[i-1][j];
                }
            }
        }

        return dp[len][a];

    }

}
